package com.captain.special.二叉树.中等;

import com.captain.leetcode.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Des:
 *
 * @author XL
 * @Date 2022/5/21 15:19
 */
public class 寻找重复的子树652 {
    public static void main(String[] args) {
        List<TreeNode> treeNodes = new 寻找重复的子树652().findDuplicateSubtrees(TreeNode.spanningTree(new Integer[]{0,0,0,0,null,null,0,null,null,null,0}));
        for (TreeNode treeNode : treeNodes) {
            System.out.println(treeNode);
        }
    }

    List<TreeNode> ans;
    Map<String, Integer> map;
    Map<TreeNode, String> checkMap;

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        //序列化每个节点
        ans = new ArrayList<>();
        map = new HashMap<>();
        checkMap = new HashMap<>();
        recur(root);
        return ans;
    }

    public void recur(TreeNode node) {
        if (node == null) {
            return;
        }
        recur(node.left);
        String childTree;
        if (checkMap.get(node) != null) {
            childTree = checkMap.get(node);
        } else {
            StringBuilder builder = recurStr(node);
            childTree = builder.toString();
        }
        map.put(childTree, map.getOrDefault(childTree, 0) + 1);
        if (map.get(childTree) == 2) {
            ans.add(node);
        }
        recur(node.right);
    }

    public StringBuilder recurStr(TreeNode node) {
        StringBuilder builder = new StringBuilder();
        if (node == null) {
            builder.append("#");
            builder.append(",");
            return builder;
        }
        builder.append(node.val);
        builder.append(",");
        StringBuilder str = recurStr(node.left);
        builder.append(str);
        StringBuilder str1 = recurStr(node.right);
        builder.append(str1);
        checkMap.put(node, builder.toString());
        return builder;
    }
}
